﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace Utilities
{
    /// <summary>
    /// A linked list.
    /// Immutable and thread-safe iff <typeparamref name="A"/> is such.
    /// </summary>
    /// <typeparam name="A">What the list contains</typeparam>
    public abstract class FList<A> : IEnumerable<A>
    {
        private static readonly FList<A> s_UniqueEmpty = new _Empty();

        /// <summary>
        /// Prepends <paramref name="h"/> to the start of list <paramref name="t"/>. O(1)
        /// </summary>
        public static FList<A> Cons(A h, FList<A> t)
        {
            return new _Cons(h, t);
        }

        /// <summary>
        /// Prepends <paramref name="h"/> to the start of this list. O(1)
        /// </summary>
        public FList<A> Cons(A h)
        {
            return new _Cons(h, this);
        }

        /// <summary>
        /// Gets the unique empty list. O(1)
        /// </summary>
        public static FList<A> Empty
        {
            get { return s_UniqueEmpty; }
        }

        /// <summary>
        /// Gets whether the list is empty. O(1)
        /// </summary>
        public abstract bool IsEmpty { get; }

        /// <summary>
        /// Gets the length of the list. O(n)
        /// </summary>
        public int Length
        {
            get
            {
                int length = 0;

                foreach (A _ in this)
                {
                    length++;
                }

                return length;
            }
        }

        /// <summary>
        /// Gets whether the list contains an element (using Equals). O(n)
        /// </summary>
        public bool Contains(A element)
        {
            foreach (A a in this)
            {
                if (element.Equals(a))
                {
                    return true;
                }
            }

            return false;
        }

        /// <summary>
        /// Creates a list from the given <see cref="IEnumerable{T}"/>. O(n)
        /// </summary>
        public static FList<A> FromEnumerable(IEnumerable<A> enumerable)
        {
            FList<A> list = Empty;
            foreach (A a in enumerable)
            {
                list = list.Cons(a);
            }
            return list.Rev();
        }

        /// <summary>
        /// Reverses this list. O(n)
        /// </summary>
        public FList<A> Rev()
        {
            FList<A> list = Empty;
            foreach (A a in this)
            {
                list = list.Cons(a);
            }
            return list;
        }

        /// <summary>
        /// Gets the head (first element) of the list. O(1)
        /// </summary>
        public abstract A Head { get; }

        /// <summary>
        /// Gets the tail (all elements but the first) of the list. O(1)
        /// </summary>
        public abstract FList<A> Tail { get; }

        /// <summary>
        /// Indexes into the list. O(n)
        /// </summary>
        public abstract A this[int index] { get; }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public IEnumerator<A> GetEnumerator()
        {
            for (FList<A> list = this; !list.IsEmpty; list = list.Tail)
            {
                yield return list.Head;
            }
        }

        public override string ToString()
        {
            const string separator = ";";

            StringBuilder sb = new StringBuilder();

            sb.Append("[");

            if (!IsEmpty)
            {
                foreach (A a in this)
                {
                    sb.Append(a);
                    sb.Append(separator);
                }

                sb.Length -= separator.Length;
            }

            sb.Append("]");

            return sb.ToString();
        }

        private sealed class _Empty : FList<A>
        {
            private const string c_EmptyErrorMessage = "Operation not valid on empty list";

            public override bool IsEmpty
            {
                get { return true; }
            }

            public override A Head
            {
                get { throw new InvalidOperationException(c_EmptyErrorMessage); }
            }

            public override FList<A> Tail
            {
                get { throw new InvalidOperationException(c_EmptyErrorMessage); }
            }

            public override A this[int index]
            {
                get { throw new IndexOutOfRangeException(); }
            }
        }

        private sealed class _Cons : FList<A>
        {
            private readonly A m_Head;
            private readonly FList<A> m_Tail;

            public _Cons(A head, FList<A> tail)
            {
                if (tail == null) throw new ArgumentNullException("tail");
                m_Head = head;
                m_Tail = tail;
            }

            public override bool IsEmpty
            {
                get { return false; }
            }

            public override A Head
            {
                get { return m_Head; }
            }

            public override FList<A> Tail
            {
                get { return m_Tail; }
            }

            public override A this[int index]
            {
                get
                {
                    foreach (A a in this)
                    {
                        if (index-- == 0)
                        {
                            return a;
                        }
                    }

                    throw new IndexOutOfRangeException();
                }
            }
        }
    }
}
